# coding:utf-8
from collections import OrderedDict


# gold mine
# TODO: 字典继承
class GM(dict):
    def __init__(self, **kwargs):
        pass

    def __setitem__(self, key, value):
        print(key)
        assert isinstance(key, tuple), "元组 or 列表"
        self.key = value

    def __getitem__(self, item):
        assert isinstance(item, list or tuple), "元组 or 列表"
        return self


# 黄金矿工
# 备忘录算法
def gold_mine(N, G: list, P: list):
    def gmine(gm:dict,n, w):
        if w < P[0] and n <= 1:
            return 0
        elif w >= P[0] and n == 1:
            return G[0]
        elif n > 1 and w < P[n - 1]:
            if (n-1,w) in gm.keys():
                return gm.get((n-1,w))
            else:
                f = gmine(gm,n-1,w)
                gm[(n-1,w)] = f
                return f
        elif n > 1 and w >= P[n-1]:
            if (n-1,w) in gm.keys():
                one = gm.get((n-1,w))
            else:
                f = gmine(gm,n-1,w)
                gm[(n-1,w)] = f
                one = f
            if (n-1,w-P[n-1]) in gm.keys():
                two = gm.get((n-1,w-P[n-1]))
            else:
                f = gmine(gm,n-1,w-P[n-1])
                gm[(n-1,w-P[n-1])] = f
                two = f + G[n-1]
            return max(one,two)
    gm = {}
    print(gmine(gm,5,10))


# 动态规划
def GOLDMINE(G,P):
    ls= [0,0,0,0,400,400,400,400,400,400]
    for row in range(1,5):
        t = []
        for col in range(1,11):
            if col >= P[row]:
                one = ls[col-1]
                # REW: 找规律
                two = G[row] if col - P[row] == 0 else ls[col - P[row] - 1] + G[row]
                t.append(max(one,two))
            else:
                t.append(ls[col-1])
        ls = t
    print(ls,'\n',ls[-1])


G = [400,500,200,300,350]
P = [5,5,3,4,3]
N = 1750
gold_mine(N,G,P)
GOLDMINE(G,P)